package net.tp.algo.compress;

import net.tp.algo.heap.BinaryHeap;
import net.tp.struct.tree.TreePrinter;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 
 * 
 * 
 * @author Trung Phan
 *
 */
public class HuffmanCode {

	public static final int R = 256;
	
	public static byte[] compress(String text) {
		
		int[] freq = new int[R];
		for (int i = 0; i < text.length(); i++) {
			freq[text.charAt(i)]++;
		}
		
		Node root = buildTree(freq);
		
		return null;
		
	}
	
	private static Node buildTree(int[] freq) {
		
		BinaryHeap<Node> heap = new BinaryHeap<>();
		
		for (int i = 0; i < R; i++) {
			if (freq[i] > 0) {
				heap.add(new Node((char)i, freq[i], null, null));
			}
		}
		
		while (true) {
			Node n1 = heap.removeHead();
			if (heap.empty()) {
				return n1;
			}
			Node n2 = heap.removeHead();
			heap.add(new Node('\0', n1.freq + n2.freq, n1, n2));
		}
	}
	
	
	
	
	
	
	
	public static class Node implements Comparable<Node> {
		private int freq;
		private char c;
		private Node left; // bit = 0 (or false)
		private Node right; // bit = 1 (or true)
		
		public Node(char c, int freq, Node left, Node right) {
			this.c = c;
			this.freq = freq;
			this.left = left;
			this.right = right;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.freq < o.freq ? -1 :
				this.freq > o.freq ? 1 : 0;
		}

        @Override
        public String toString() {
            return TreePrinter.toString(this,
                    (n) -> n.c == '\0' ? "-" : Character.valueOf(n.c).toString(),
                    (n) -> Arrays.asList(n.left, n.right));
        }
		
	}
	
	
}
